#include "LinkList.h"
#include <iostream>

//成员变量的初始化在初始化列表中，其余初始化在花括号里面 
LinkList::LinkList():head(new Node),size(0)
{
    //头指针不会置为空
    //没有头节点就是一个指针，就没有head->next
    head->data = 0;
    head->next = nullptr;     
}

LinkList::~LinkList()
{
    while(head != nullptr)//头节点不为空一定存在一个指针域
    {
        Node * nextNode = head->next;//记下下一个节点
        delete head;//释放现在节点
        head = nextNode;//把下一个变成现在的
    }//循环去判断，去释放
}

//创建新节点的函数
//内联函数在编译时候会把代码展开，只适合简单函数
inline Node* CreateNode(ElementType element)
{
    Node * newNode = new Node;//插入数据就要创建一个新的节点
    newNode->data = element;//把数据插入节点
    newNode->next = nullptr;//尾插之后我是最后一个，所以指向null
    return newNode;//注意返回值为newNode
    
}

//尾插法
void LinkList::InsertTail(ElementType element)//o(n)
{
    
    Node * travelPoint = head;//遍历指针，代替head往后走
    while(travelPoint->next != nullptr)//不是最后一个节点
    {
        travelPoint = travelPoint->next;//节点继续往后走
    }
    travelPoint->next = CreateNode(element);//指向新插入的节点
    size++;
}

//头插法
void LinkList::InsertHead(ElementType element)//o(1)
{
    Node * newNode = CreateNode(element);
    newNode->next = head->next;//要先接住head的后一个节点
    head->next = newNode;//在用head指向插入的新节点
    size++;
}

//按位置插入
void LinkList::InsertByIndex(int index, ElementType element)
{
    //插入第n个位置，要找n-1的位置
    Node * travelPoint = head;
    for(int i = 0; i < index; i++)//index都是从0开始,我们要插在index-1后面
    {
        travelPoint = travelPoint->next;
    }
    Node * newNode = CreateNode(element);
    newNode->next = travelPoint->next;
    travelPoint->next = newNode;
    size++;
}
//按位置删除
void LinkList::RemoveByIndex(int index)//o(n)
{
    Node * travelPoint = head;
    for(int i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }
    //要释放原index位置空间,先把节点记下来
    Node *freeNode = travelPoint->next;
    travelPoint->next = freeNode->next;
    delete freeNode;
    size--;
}
//按数值删除
void LinkList::RemoveByElement(ElementType element)
{
    Node * travelPoint = head;
    while(travelPoint->next != nullptr)//遍历到最后
    {
        if(travelPoint->next->data == element)
        {
            Node *freeNode = travelPoint->next;
            travelPoint->next = freeNode->next;
            delete freeNode;
            size--;
        }
        else
            travelPoint = travelPoint->next;//当前和下一个不相等才往后走
    }
}

//按位置修改
void LinkList::UpdataByIndex(int index, ElementType newValue)
{
    Node * travelPoint = head;
    for(int i = 0; i <= index; i++)//停在index当前位置
    {
        travelPoint = travelPoint->next;
    }
    travelPoint->data = newValue;
}

//按数值修改
void LinkList::UpdataByElement(ElementType oldValue, ElementType newvalue)
{
    Node * travelPoint = head;
    while(travelPoint->next != nullptr)//当下一个指针不为空则继续遍历
    {
        //travelPoint后面加next，这样才能判断到nullptr的前一位，不加的话会漏掉
        if(travelPoint->next->data == oldValue)//判断是否与oldValue相等 
        {
            travelPoint->next->data = newvalue;//如相等直接修改值
        }
        //只是修改了值，指针没动，所以不用加else
        travelPoint = travelPoint->next;//往后走，有相同值的时候才会继续修改
    }
}

//按位置查找值
ElementType &LinkList::operator[](int index)//加引用可以直接修改该位置的值
{
    Node * travelPoint = head;
    for(int i = 0; i <= index; i++)//停在index当前位置
    {
        travelPoint = travelPoint->next;
    }
    return travelPoint->data;//返回当前值
}

//冒泡排序：两两比较，把较大的数值都放在左边
void LinkList::BubbleSort()
{
    //size不包含头节点
    for(int i = 0; i < size - 1; i++)//对每一个进行扫描,但是最后一个不用扫描 
    {
        Node * travelPoint = head;//每次扫描数列后都会回到起始点
        for(int j = 0; j < size - i - 1; j++)//两两比较 //比完一个循环就少一个节点
        {
            if(travelPoint->next->data > travelPoint->next->next->data)
            {
                Node *Prev = travelPoint->next;
                Node *Next = Prev->next;
                //可以直接换数据域，但是不够灵活，所以我们更倾向于更换节点
                //交换顺序不能变，先接住下面的链表
                Prev->next = Next->next;
                Next->next = Prev;
                travelPoint->next = Next;
            }
            travelPoint = travelPoint->next;
        }
    }
}

//归并；归并的前提是先排序，传入的是链表，返回的也是链表
LinkList LinkList::Merge(const LinkList &l)
{
    //双指针
    LinkList result;
    Node * p1 = this->head->next;
    Node * p2 = l.head->next;
    while(p1 && p2)//while(p1 != nullptr && p2 != nullptr)
    {
        if(p1->data < p2->data)
        {
            result.InsertTail(p1->data);//谁小插入谁
            p1 = p1->next;
        }
        else  
        {
            result.InsertTail(p2->data);
            p2 = p2->next;
        }   
    }
    while (p1)//p2为nullptr但是p1不是
    {
        result.InsertTail(p1->data);
        p1 = p1->next;
    }
    while(p2)//p1为nullptr但是p2不是
    {
        result.InsertTail(p2->data);
        p2 = p2->next;
    }
    return result;
}
//链表的逆序：三指针
void LinkList::Reserve()
{
    Node * prev = nullptr;
    Node * cur = head->next;
    Node * Next = cur->next;
    while(Next != nullptr)
    {
        cur->next = prev;//每次只逆c
        prev = cur;
        cur = Next;
        Next = cur->next;//p,c,n往后走
    }
    cur->next = prev;
    head->next = cur;//新的头指向原来的尾巴
}


//链表的逆序：递归，保存每一个节点的位置
Node *LinkList::Reserve2(Node *node)
{
    //终止条件
    if(node->next == NULL)//原来的尾巴
    {
        return node;//变成头
    }
    else
    {
        Node * newHeader = Reserve2(node->next);//newHeader从头没有变
        node->next->next = node;
        node->next = nullptr;//为了让最后一个节点指向空
        return newHeader;
    }
}
//调用递归逆序
void LinkList::Reserve2()
{
    head->next = Reserve2(head->next);
}

Node *LinkList::GetEnd() // 重新听这部分
{
    Node * travelPoint = head;
    while(travelPoint->next != nullptr)
        travelPoint = travelPoint->next;
    return travelPoint;
}

//封装的FastSort函数：
void LinkList::FastSort(Node *start, Node *end)
{
    if(start == end)//双指针相遇
        return;
    Node * temp = start;//基准值
    Node * p1 = start;//left
    Node * p2 = p1->next;//right

    while(p2 != end)
    {
        if(p2->data < temp->data)//比基准值小
        {
            p1 = p1->next;//p1往后挪一位
            //不确定中间又多少节点，所以直接换值
            std::swap(p1->data,p2->data);
        }
        p2 = p2->next;
    }
    std::swap(p1->data,temp->data);//将基准值和p1的值互换
    //p1左边都比基准值小，右边都比基准值大
    FastSort(start,p1);
    FastSort(p1->next,end);
}

//调用FastSort函数
void LinkList::FastSort()
{
    FastSort(head->next,nullptr);//p2到end就不会进去了，所以也不会进去空指针，只到空指针之前
}

void LinkList::show()
{
    Node * travelPoint = head;
    while(travelPoint->next != nullptr)//头节点不放有效数据
    {
        std::cout<<travelPoint->next->data<<" ";
        travelPoint = travelPoint->next;//继续访问下一个节点
    }
    std::cout<<std::endl;
}


